package binarysearch.搜索二维矩阵;

/**
 * 给你一个满足下述两条属性的 m x n 整数矩阵：
 * <p>
 * 每行中的整数从左到右按非严格递增顺序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
 */
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        return search(matrix, 0, m * n -1 , target);
    }

    boolean search(int[][] matrix, int start, int end, int target) {
        if (start > end) {
            return false;
        }
        int midIndex = (start + end) / 2;
        int midIndexRow = midIndex / matrix[0].length;
        int midIndexClo = midIndex % matrix[0].length ;
        if (matrix[midIndexRow][midIndexClo] == target) {
            return true;
        } else if (matrix[midIndexRow][midIndexClo] < target) {
            return search(matrix, midIndex + 1, end, target);
        } else {
            return search(matrix, start, midIndex - 1, target);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
        System.out.println(solution.searchMatrix(new int[][]{{1 , 3 }}, 5));

    }
}
